//
// Created by lanlu on 2025/8/7.
//

#include <vector>
#include <stack>
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr)
    {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr)
    {
    }

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right)
    {
    }
};


class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> s;
        // 记录当前遍历到节点
        TreeNode* cur = root;
        // 记录上一次访问的节点
        TreeNode* prev = nullptr;

        while (cur != nullptr || !s.empty())
        {
            while (cur != nullptr)
            {
                s.push(cur);
                cur = cur->left;
            }

            // 查看栈顶节点 但不取出
            cur = s.top();
            // 只有当前节点的右子树为空或者已经访问过 才取出
            if (cur->right == nullptr || cur->right == prev)
            {
                s.pop();
                result.push_back(cur->val);
                // 更新上一次访问的节点
                prev = cur;
                // 将当前节点置空 下一次从栈顶节点开始遍历
                cur = nullptr;
            }
            else
            {
                cur = cur->right;
            }
        }
        return result;
    }
};